// #include"AVLtree.h"

// void test01()
// {
// 	int a[] = { -16, 3, 7, -11, -9, 26, 18, -14, -15 };
// 	AVLtree<int> t;
// 	for (auto e : a) t.insert(e);
// 	for (auto it = t.begin(); it != t.end(); ++it)
// 		cout << *it << ' ';
// 	cout << endl;
// }

// struct my_cmp
// {
// 	// 按绝对值大小比较
// 	bool operator()(int a, int b) const
// 	{
// 		return abs(a) < abs(b);
// 	}
// };
// void test02()
// {
// 	int a[] = {-16, 3, 7, -11, -9, 26, 18, -14, -15};
// 	AVLtree<int> t;
// 	AVLtree<int, my_cmp> t1;

// 	for (auto e : a)
// 	{
// 		t.insert(e);
// 		t1.insert(e);
// 	}

// 	for (auto e : t)
// 		cout << e << ' ';
// 	cout << endl;
	
// 	for (auto e : t1)
// 		cout << e << ' ';
// }

#include"set_map.h"

// struct my_cmp
// {
// 	// 按绝对值大小比较
// 	bool operator()(const pair<int,int>& a, const pair<int,int>& b) const
// 	{
// 		if(a.first != b.first)
// 			return a.first > b.first;
// 		return a.second > b.second;
// 	}
// };
// 
// void test_set01()
// {
// 	set<pair<int,int>, my_cmp> s;
// 	// int a[] = {-16, 3, 7, -11, -9, 26, 18, -14, -15};
// 	pair<int,int> a[] = { {-16, 3}, {7, -11}, {-9, 26}, {18, -14}, {-15,15} };
// 	for(auto e : a)
// 		s.insert(e);

// 	for(auto& e : s)
// 	{
// 		cout << e.first << ' ' << e.second << endl;
// 		// e = 10;
// 	}
// }

void test_set02()
{
    set<int> s = { 2,3,5,6,7,9 };

    auto it = s.find(3);    // 查找元素3。找到了返回指向元素的迭代器，否则返回s.end()
    cout << *it << endl;

    it = s.lower_bound(5);  // 查找第一个 >= 5 的元素，找到了返回其迭代器，否则返回s.end();
    cout << *it << endl;

    it = s.upper_bound(5);  // 查找第一个 > 5 的元素，找到了返回其迭代器，否则返回s.end();
    cout << *it << endl;

    int cnt = s.count(4);   // 查询容器种元素4的个数。对于set而言，找到了返回1，否则返回0
    cout << cnt << endl;
    cnt = s.count(5);
    cout << cnt << endl;
}

void test_set03()
{
    set<int> s;
    int a[] = { 2,3,5,6,7,9 };
    for(auto e : a)     
        s.insert(e);    // 把a数组的所有元素插入到s种
    
    auto p = s.insert(2);
    // insert的返回值：
    // 成功插入返回 pair<插入元素的迭代器, true>，否则返回 pair<插入元素的迭代器, false>
    cout << *(p.first) << " " << p.second << endl;

    p = s.insert(999);
    cout << *(p.first) << " " << p.second << endl;
}

struct my_cmp
{
	// 按绝对值大小比较
	bool operator()(int a, int b) const
	{
		return abs(a) < abs(b);
	}
};
void test_set04()
{
    set<int, my_cmp> s = { 2,-3,5,-6,7,-9 };
    int cnt = s.erase(2);   // 删除2。
    // erase的返回值是成功删除的元素个数。对于set而言成功删除返回1，否则返回0
    cout << cnt << endl;
    for(auto& e : s) cout << e << ' ';
    cout << endl;

    cnt = s.erase(3);
    cout << cnt << endl;
    for(auto& e : s) cout << e << ' ';
    cout << endl;

	set<int, my_cmp> s1(s.begin(), s.end());
	for(auto& e : s1) cout << e << ' ';
    cout << endl;
}

void test_map01()
{
    map<string, int> m;     // 默认构造
    pair<string, int> p[3] = { {"baa", 5}, {"ab", 2}, {"ccc", 1} };
    map<string, int> m1(p, p + 3);  // 迭代器区间构造

    map<string, int> m2 = { {"c", 2}, {"b", 1}, {"a", 7} };   // 列表构造

    for(auto& p : m)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;

    for(auto& p : m1)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;

    for(auto& p : m2)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;

	// map<int, int, greater<int>> m = { {1,0}, {2,0}, {3,0} };	// 按key升序
    // for(auto& p : m)
    //     cout << p.first << ' ' << p.second << endl;
    // cout << endl;
}

void test_map02()
{
    map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };
    for(auto& p : m)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;

    auto it = m.find("sort");   // 查找key为sort的元素。找到了返回该元素的迭代器，否则返回m.end()
    cout << it->first << " " << it->second << endl;
    it = m.find("xxx");
}

// void test_map03()
// {
//     map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };
    
//     auto it = m.insert({"age", "年龄"});    // m内部元素类型为pair<string,string>，插入的元素类型应当也是pair<string,string>
//     // insert的返回值：
//     // 成功插入返回 pair<指向该元素的迭代器, true>，否则返回pair<指向该元素的迭代器, false>
//     cout << it.first->first << ' ' <<  it.first->second << ' ' << it.second << endl;

//     it = m.insert({"left", "剩余"});    // m中已经有key值为"left"的元素了，这里会插入失败
//     cout << it.first->first << ' ' <<  it.first->second << ' ' << it.second << endl;
// }

void test_map03()
{
    map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };

    // 1.通过key查找value
    cout << m["left"] << endl;
    cout << m["right"] << endl;
    cout << m["sort"] << endl << endl;

    m["left"] = "剩余"; // 修改value
    cout << m["left"] << endl << endl;

    // 2.充当插入
    m["word"] = "单词"; // 插入{"word", "单词"}。【其实应该是先插入{"word", string()}, 然后再将value修改为"单词”】
    m["who"];       // 没有给value，会用其默认构造，相当于插入{"who", string()}

    for(auto& p : m)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;
}

void test_map04()
{
    map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };

    int cnt = m.erase("left"); // 删除key为left的元素。返回成功删除的元素个数，对map而言：成功删除返回1，否则返回0
    cout << cnt << endl;

    for(auto& p : m)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;
}

void test_map05()
{
    map<int, int> m = { {2,3}, {5,6}, {7,9} };  // m存储的元素类型为 pair<int,int>
	cout << m[2] << endl;
    // 1.迭代器。begin()返回第一个元素的迭代器；end()返回最后一个元素的下一个元素的迭代器
    auto it = m.begin();
    while(it != m.end())
    {
        cout << it->first << ' ' << it->second << endl;
        // cout << (*it).first << ' ' << (*it).second << endl; // 也可以这样写。it是指向 pair<int,int> 的迭代器

        // it->first = 999;  // err 注意：key不可修改
        it->second = 999;  // err 注意：key不可修改
        ++it;
    }

    // 2.容量相关
    cout << m.size() << endl;   // 返回容器里的元素个数
    cout << m.empty() << endl;  // 判断容器里是否为空。为空返回true，否则返回false
    m.clear();  // 清空容器
	cout << m.size() << endl;   // 返回容器里的元素个数
    cout << m.empty() << endl;
}
void test_map06()
{
	int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
	map<int, int, greater<int>> m;
	for(auto e : a)
		m.insert({e, 0});
	for(auto& p : m)
		cout << p.first << ' ';
	cout << endl;

	cout << m[5] << endl;
	cout << m.erase(5) << endl;
	cout << m.erase(0) << endl;
	cout << m.erase(16) << endl;
	cout << m.erase(11) << endl << endl;
	for(auto& p : m)
		cout << p.first << ' ';
	cout << endl;
}

void test_map07()
{
	map<int, int> m = {{16, 3}, {7, 11}, {9, 26}, {18, 14}};
	auto it = m.find(16);
    cout << it->first << ' ' << it->second << endl;
    m[16] = 5;
    cout << it->first << ' ' << it->second << endl;

}
#include<ctime>

int main()
{
	int b = clock();
    test_map04();
	int e = clock();
	cout << e - b << endl;
    return 0;
}
